#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    private:
    int index = 0;

    public:
    int ans1(vector<int>& nums){
        int len = nums.size();
        if(len == 1){
            return 0;
        }
        if(len == 2){
            if(nums[0] == max(nums[0], nums[1])){
                return 0;
            }else{
                return 1;
            }
        }
        for(int i = 1; i != len-1; i++){
            if(nums[i] > nums[i-1] && nums[i] > nums[i+1]){
                return i;
            }
        }
        if(nums[0] == *max_element(nums.begin(), nums.end())){
            return 0;
        }else{
            return len-1;
        }
    }

    //递归+二分
    int ans2(vector<int>& nums){
        int len = nums.size();
        int left = 0, right = len-1;
        fun(left, right, len, nums);

        return index;

    }

    void fun(int left, int right, int len, vector<int>& nums){
        if(left > right){
            return;
        }
        int mid = left + (right - left) / 2;
        if(mid > 0 && mid < len-1){
            if(nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]){
                index = mid;
                return;
            }
        }else if(mid == 0){
            if(nums[mid] > nums[mid+1]){
                index = mid;
                return;
            }
        }else{
            if(nums[mid] > nums[mid-1]){
                index = mid;
                return;
            }
        }
        fun(left, mid-1, len, nums);
        fun(mid+1, right, len, nums);
    }

};

void test(){
    Solution s;
    vector<int> nums = {1,2,3,1,4,1};

    int ret = s.ans2(nums);
    cout << ret << endl;
}

int main(void){
    test();

    return 0;
}